#include<bits/stdc++.h>
using namespace std;
int t;
int a[200005];
int ans=0;
int dfs(int idx,int c[20],int nm)
{
    if(idx==nm+1)
    {
        int cnt=0;
        for(int i=1;i<=nm;i++)
        {
            for(int j=i-1;j>=1;j--)
            {
                if(c[j]==c[i]&&a[j]==a[i])
                {
                    cnt+=a[j];
                }
            }
        }
        ans=max(ans,cnt);
        return 0;
    }
    c[idx]=0;
    dfs(idx+1,c,nm);
    c[idx]=1;
    dfs(idx+1,c,nm);
    return 0;
}
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        int vis[2005],r[2005],l[2005];
        int idx=0;
        for(int i=1;i<=n;i++)
        {
            cin >> a[i];
            r[a[i]]=i;
            vis[a[i]]++;
            if(vis[a[i]]==1)
            {
                l[a[i]]=i;
                idx++;
            }
        }
        ans=0;
        if(n<=20)
        {
            int tmp[20];
            memset(tmp,0,sizeof(tmp));
            ans=0;
            dfs(2,tmp,n);
            tmp[1]=1;
            dfs(2,tmp,n);
            cout << ans << endl;
        }
        else
        {
            int c[1000005];
            int t=0;
            for(int i=idx;i>=1;i--)
            {
                if(vis[i]>=2)
                {
                    int cnt=(vis[i]-1)*i;
                    int flag[5];
                    for(int j=r[i];j>=l[i];j--)
                    {
                        if(c[j])
                        {
                            flag[c[j]]++;
                            if(flag[c[j]]&&(flag[c[j]-1]||flag[c[j]+1]))
                            {
                                cnt-=i;
                            }
                        }
                        c[j]=1;
                    }
                    ans+=cnt;
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}
